The channel used in telecommunications systems frequently causes interference in data transmission. Interference occurs in all kinds of systems but particularly in wireless telecommunications systems the transmission path attenuates and distorts the signal to be transmitted in various ways. On the transmission path interference is typically caused by multi-path propagation of the signal and different kinds of fading and reflection as well as by other signals transmitted on the same transmission path.
To reduce the influence of interference, different coding methods have been provided to protect signals from interference and to eliminate errors caused by interference in the signals. One frequently used encoding method is convolutional encoding. In convolutional encoding the signal to be transmitted and consisting of symbols is encoded into code words, which are based on the convolution of the symbols to be transmitted with themselves or with another signal. The convolutional code is defined by the coding ratio and coding polynomials. The coding ratio (k/n) means the number (n) of encoded symbols in relation to the number (k) of symbols to be encoded. The coder is usually implemented by means of shift registers. The constraint length K of the code refers to the degree of coding polynomials plus one. The coder may be regarded as a state machine with 2K-1 states.
One coding method developed from convolutional coding methods is parallel concatenated convolutional code, i.e. a turbo code. One way of forming a turbo code is to use two recursive and systematic convolutional encoders and interleavers. The resulting code includes a systematic part, which directly corresponds to symbols in the coder input, and two parity parts, which are the outputs of the parallel convolutional encoders.
A signal which has propagated on a channel is decoded in a receiver. The convolutional code can be both encoded and decoded using a trellis whose nodes (or equally states) correspond to the states of the encoder used in signal encoding and the paths between nodes belonging to two successive trellis phases of the trellis correspond to allowed state transitions between the encoder states. The code unequivocally attaches the initial and the final state of the transition, the bit under encoding and the bits of the encoding result to each state transition. The purpose of the decoder is thus to determined successive states of the coder, i.e. transitions from one state to another, which are caused by the original bits. To determine the transitions, metrics are calculated in the decoder. There are two kinds of metrics: path metrics (also state metrics) and branch metrics. The path metrics represents the probability at which the set of symbols included in the received signal leads to the state corresponding to the node in question. The branch metrics is proportional to the probabilities of transitions.
A Viterbi algorithm is usually used in decoding of a convolutional code. An example of a decoding method which requires more intensive calculation is a MAP (Maximum Aposteriori Probability) algorithm and its variations, e.g. Log MAP algorithm or Max Log MAP algorithm. The MAP algorithm is also known as a BCJR algorithm (Bahl, Cocke, Jelinik and Raviv) according to the persons who presented it first. Usually the MAP algorithm and its variations provide a considerably better result than the Viterbi algorithm. Furthermore, since the MAP algorithm and its variations are SISO algorithms (Soft Input Soft Output), they are particularly suited for iterative decoding, e.g. for decoding a turbo code where a posteriori probabilities can be utilized. The basic Viterbi algorithm is a Hard Output algorithm which has to be converted to obtain soft decisions, which increases its calculation complexity. Thus the algorithm obtained through conversion is not as good as MAP-based algorithms.
To estimate a posteriori probabilities, the MAP algorithm and its variations usually require path metrics for each bit to be decoded both from the beginning of the trellis to its end and from its end to its beginning at the bit in question. According to the prior art, the values of the path metrics of all nodes are stored in a memory in each trellis phase in respect of one direction, e.g. forwards, and then values are calculated for the other direction, e.g. backwards. The problem associated with this solution is that it requires a lot of memory because all path metrics of one direction are stored in the memory so as to allow their utilization with the path metrics to be calculated in the other direction.
U.S. Pat. No. 5,933,462, which is incorporated herein by reference, describes use of a sliding window to reduce the memory requirement. The solution comprises calculating and storing forward path metrics in respect of a window with a certain constant length and then reading them in inverse order with the backward path metrics for further measures. A solution based on the same principle is described in H. Dawid and H. Meyr: Real-Time Algorithms and VLSI Architectures for Soft Output Map Convolutional Decoding in 6th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Toronto, Canada, Volume 1, pp. 193–197, September 1995.
Another prior art solution is to use the Log MAP algorithm instead of the Max Log MAP algorithm to invert the original calculation direction of path metrics, which makes additional memory unnecessary. The solution is described in S. Huettinger, M. Breiling and J. Huber: Memory Efficient Implementation of the BCJR Algorithm in Proceedings of the 2nd International Symposium on Turbo Codes and Related Topics, Brest, France, 4–7 Sep. 2000. The problem associated with this solution is that the path metrics calculated in the inverse direction are not accurate due to the solving method used but cause errors in the values of path metrics. Furthermore, implementation of the Log MAP algorithm is more complicated than that of the Max Log MAP algorithm although the capacity of the Log MAP algorithm is slightly better than that of the Max Log MAP algorithm.
To sum up, there is a great need to solve backward processing of a trellis opposite to the actual processing direction using the memory as efficiently as possible without impairing the quality of the result.